package com.kabu.redlbacktree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author jiawuwei
 * @Copyright: Copyright (c) 兆日科技股份有限公司  2020
 * @date 2020/8/14,9:31
 */
public class RedBlackTree<K extends Comparable<K>, V> {
    private final boolean RED = true;
    private final boolean BLACK = false;
    Node root;
    class Node<K extends Comparable<K>,V> {
        Node parent;
        public Node left;
        Node right;
        boolean color;
        K key;
        V value;
        public Node(){}

        @Override
        public String toString() {
            return "Node{" +
                    "parent=" + parent +
                    ", left=" + left +
                    ", right=" + right +
                    ", color=" + color +
                    ", key=" + key +
                    ", value=" + value +
                    '}';
        }

        public Node(Boolean col, K key, V value, Node parent, Node left, Node right) {
            this.color = col;
            this.key = key;
            this.value = value;
            this.parent = parent;
            this.left = left;
            this.right = right;

        }
    }

    private Node parentOf(Node node) {
        if (node != null) {
            return node.parent;
        }
        return null;
    }

    private boolean isRed(Node node) {
        if (node != null) {
            return node.color == RED;
        }
        return false;
    }
    private boolean isBlack(Node node) {
        if (node != null) {
            return node.color == BLACK;
        }
        return true;
    }
    private void setRed(Node node){
        if(node!=null){
            node.color=RED;
        }
    }
    private void setBlack(Node node){
        if(node!=null){
            node.color=BLACK;
        }
    }
    public void inOrderPrint(){
        inOrderPrint(this.root);
    }
    public void inOrderPrint(Node node){
        if(node!=null){
            inOrderPrint(node.left);
            System.out.println("key: "+node.key+",value"+node.value);
            inOrderPrint(node.right);
        }
    }

    /**
     *     pp               pp
     *     |                |
     *     p                r
     *   /   \    -->     /  \
     *  pl    r          p    rr
     *      /  \        /  \
     *     rl   rr     pl  rl
     *  左旋代码：左旋节点为p，自己是r，左儿子是rl，父亲是p，爷爷是pp
     * 1.儿子给爷爷：将p的右子节点指向r的左子节点（rl),将r的左子节点的父亲更新为p
     * 2.自己给爷爷：当p的父节点（不为空时），更新y的父节点为p的父节点(pp)，并为p的父节点(pp)指定子树（当前p的子树位置）指定为r，为空时重新指向root
     * 3.爸爸给自己：将p的父节点更新为r，将r的左子节点更新为p
     */
    private void leftRotate(Node p) {
        Node r = p.right;
        //1.儿子给爷爷：将p的右子节点指向r的左子节点（rl),将r的左子节点的父亲更新为p
        p.right = r.left;
        if(r.left!=null){
            r.left.parent = p;
        }
        //2.自己给爷爷：当p的父节点（不为空时），更新y的父节点为p的父节点(pp)，并为p的父节点(pp)指定子树（当前p的子树位置）指定为r，为空时重新指向root
        if(p.parent!=null){
            r.parent = p.parent;
            if(p==p.parent.left){
                p.parent.left = r;
            }else{
                p.parent.right =r;
            }
        }else{
            this.root = r;
            this.root.parent = null;
        }
        //3.爸爸给自己：将p的父节点更新为r，将r的左子节点更新为p
        p.parent = r;
        r.left = p;

    }


    /**
     *     pp               pp
     *     |                |
     *     p                l
     *   /   \    -->     /   \
     *  l    pr          ll    p
     * /  \                   / \
     *ll  lr                 lr  pr
     *  右旋代码：右旋p节点，自己是l，爸爸是p，爷爷是pp，右儿子是lr
     * 1.儿子给爷爷：将p的左子节点指向l的右子节点lr，将l的右子节点的父亲更新为p
     * 2.自己给爷爷：当p的父节点不为空时，更新l的父亲节点为p的父节点(pp)，并指定p的父节点(pp)的子树为l，为空时重新指向root
     * 3.爸爸给自己：将p的父亲节点更新为l，将l的右子节点更新为p
     *
     */
    private void rightRotate(Node p) {
        Node l = p.left;
        //1.儿子给爷爷：将p的左子节点指向l的右子节点lr，将l的右子节点的父亲更新为p
        p.left = l.right;
        if (l.right != null) {
            l.right.parent = p;
        }
        //2.自己给爷爷：当p的父节点不为空时，更新l的父亲节点为p的父节点(pp)，并指定p的父节点(pp)的子树为l，为空时重新指向root
        if (p.parent != null) {
            l.parent = p.parent;
            if (p == p.parent.left) {
                p.parent.left = l;
            } else {
                p.parent.right = l;
                this.root.parent = null;
            }
        } else {
            this.root = l;
        }
        //3.爸爸给自己：将p的父亲节点更新为l，将l的右子节点更新为p
        p.parent =l;
        l.right = p;
    }

    /**
     * 插入方法
     * @param key
     * @param value
     */
    public void insert(K key,V value){
        Node node = new Node();
        node.key = key;
        node.value = value;
        node.color = RED;
        insert(node);
    }

    private void insert(Node node){
        //1.找到要插入节点的父亲，然后插入,从根节点开始
        Node parent = null;
        Node t = this.root;
        while (t!=null){
            parent = t;
            int cmp = node.key.compareTo(t.key);
            if(cmp>0){
                //说明在右边，从右子树开始遍历
                t=t.right;
            }else if(cmp==0){
                t.value = node.value;
                return;
            }else {
                t=t.left;
            }
        }
        node.parent=parent;
        //找到父亲后，然后插入该节点
        if(parent!=null){
            int cmp = node.key.compareTo(parent.key);
            if(cmp>0){
                //说明在右边，从右子树开始遍历
                parent.right = node;
            }else {
                parent.left = node;
            }
        }else{
            this.root = node;
        }
        insertFixup(node);
    }

    /**
     * 1：红黑树是空树，将根节点染为黑色
     * 2：插入的节点的key已经存在，不需要处理
     * 3：插入的节点的父节点为黑色，因为你所插入的路径，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理
     * 4：插入节点的父节点为红色
     * 	4.1：叔叔节点存在并且为红色（父-叔 双红），将爸爸和叔叔染为黑色，将爷爷染为红色，并且再以爷爷节点为当前节点，进行下一轮处理
     * 	4.2：叔叔节点不存在或者为黑色，父节点为爷爷节点的左子树
     * 		4.2.1：插入节点为其父节点的左子节点（LL情况），将爸爸染为黑色，将爷爷染为红色，然后以爷爷节点右旋，就完成了
     * 		4.2.2：插入的节点为其父节点的右子节点（LR）情况，以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理
     * 	4.3：叔叔节点不存在或者为黑色，父节点为爷爷节点的右子树
     * 		4.3.1：插入节点为其父节点的右子节点（RR情况），将爸爸染为黑色，将爷爷染为红色，然后以爷爷节点左旋，就完成了
     * 		4.3.2：插入的节点为其父节点的左子节点（RL）情况，以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
     */
    private void insertFixup(Node node){
        //1：红黑树是空树，将根节点染为黑色
        this.root.color=BLACK;
        //父亲节点
        Node parent = parentOf(node);
        //4：插入节点的父节点为红色
        if(parent!=null && isRed(parent)){
            //爷爷节点,如果父亲为红色，那肯定有爷爷节点
            Node gparent = parentOf(parent);
            //叔叔节点
            Node uncle = null;
            if(parent == gparent.left){//如果爸爸是爷爷的左子树
                uncle = gparent.right;
                //4.1：叔叔节点存在并且为红色（父-叔 双红），将爸爸和叔叔染为黑色，将爷爷染为红色，并且再以爷爷节点为当前节点，进行下一轮处理
                if(uncle!=null && isRed(uncle)){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color=BLACK;
                    insertFixup(gparent);
                    return;
                }
                //4.2：叔叔节点不存在或者为黑色，父节点为爷爷节点的左子树
                if(uncle==null || isBlack(uncle)){
                    //4.2.1：插入节点为其父节点的左子节点（LL情况），将爸爸染为黑色，将爷爷染为红色，然后以爷爷节点右旋，就完成了
                    if(node == parent.left){
                        parent.color = BLACK;
                        gparent.color=RED;
                        rightRotate(gparent);
                        return;
                    }
                    //4.2.2：插入的节点为其父节点的右子节点（LR）情况，以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理
                    if(node == parent.right){
                        leftRotate(parent);
                        insertFixup(parent);
                        return;
                    }

                }

            }else{//爸爸是爷爷的右子树
                uncle = gparent.left;
                //4.1：叔叔节点存在并且为红色（父-叔 双红），将爸爸和叔叔染为黑色，将爷爷染为红色，并且再以爷爷节点为当前节点，进行下一轮处理
                if(uncle!=null && isRed(uncle)){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    gparent.color=BLACK;
                    insertFixup(gparent);
                    return;
                }
                //4.3：叔叔节点不存在或者为黑色，父节点为爷爷节点的右子树
                if(uncle==null || isBlack(uncle)){
                    //4.3.1：插入节点为其父节点的右子节点（RR情况），将爸爸染为黑色，将爷爷染为红色，然后以爷爷节点左旋，就完成了
                    if(node == parent.right){
                        parent.color = BLACK;
                        gparent.color=RED;
                        leftRotate(gparent);
                        return;
                    }
                    //4.3.2：插入的节点为其父节点的左子节点（RL）情况，以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
                    if(node == parent.left){
                        rightRotate(parent);
                        insertFixup(parent);
                        return;
                    }

                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        RedBlackTree<Integer,Object> rbt = new RedBlackTree<>();
        while (true){
            System.out.println("请输入key：");
            int key = Integer.parseInt(scanner.next());
            System.out.println();
            rbt.insert(key,null);
            TreeOperation.show(rbt.root);

        }
    }
}
